package com.macro.mall.bo;
import java.util.*;

public class Hot {

    public static ListNode getIntersectionNode(ListNode a, ListNode b) {
        ListNode a1 = a;
        ListNode b1 = b;
        int cnt =1;
        boolean flag = true;
        int len1 = 0;
        int len2 = 0;
        while(a1!=null)
        {
            len1++;
            a1 = a1.next;
        }
        while(b1!=null)
        {
            len2++;
            b1 = b1.next;
        }
        a1 =a;
        while(len1>len2)
        {
            a1= a1.next;
            len1--;
        }
        b1 = b;
        while(len2>len1)
        {
            b1=b1.next;
            len2--;
        }
        while(a!=null)
        {
            if(a==b)
            {
                return a;
            }
            a=a.next;
            b=b.next;
        }
        return null;
    }
    public static ListNode reverseList(ListNode a)
    {
        ListNode pre = null;
        ListNode cur = a;
        while(cur!=null)
        {
            ListNode curn = cur.next;
            cur.next = pre;
            pre =cur;
            cur = curn;
        }
        return pre;
    }
    public static boolean isHuiWen(ListNode a)
    {
        ListNode fast = a;
        ListNode solw = a;
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            solw  = solw.next;
        }
        if(fast!=null){
            solw = solw.next;
        }
        ListNode right =reverseList(solw);
        ListNode left = a;
        while(right!=null)
        {
            if(right.val!=right.val)
            {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        //当我们的fast！=null跳过中点时，整个长度是奇数，否则是偶数
        return true;
//     List<Integer> list = new ArrayList<>();
//     ListNode  b =a;
//     while(b!=null)
//     {
//         list.add(b.val);
//         b=b.next;
//     }
//     for(int i=0;i<list.size()/2;i++)
//     {
//        if(list.get(i)!=list.get(list.size()-1-i))
//        {
//            return false;
//        }
//
//     }
//        return true;
    }
    public static boolean hasCycle(ListNode a)
    {
        ListNode fast = a;
        ListNode solw = a;
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            solw  = solw.next;
            if(solw==fast)
                return  true;
        }
        return false;
    }
    public static ListNode merge(ListNode a, ListNode b)
    {
        ListNode root = new ListNode(0);
        ListNode cur = a;
       List<Integer> list = new ArrayList<>();
       while(cur!=null)
       {
           list.add(cur.val);
           cur = cur.next;
       }
       cur = b;
        while(cur!=null)
        {
            list.add(cur.val);
            cur = cur.next;
        }
        Collections.sort(list);
        cur = root;
        for(int i=0;i<list.size();i++)
        {
            cur.next = new ListNode(list.get(i));
            cur = cur.next;
        }
        return root.next;
    }
    public static ListNode addToNumbers(ListNode a, ListNode b)
    {
        ListNode a1 = a;
        ListNode b1 = b;
        ListNode c = new ListNode(0);
        ListNode cur  = c;
        int count  =0;
        while(a1!=null||b1!=null)
        {
            int sum=count;
            if(a1!=null)
            {
                sum+= a1.val;
                a1= a1.next;
            }
            if(b1!=null)
            {
                sum+=b1.val;
                b1 = b1.next;
            }
            count  =sum/10;
            cur.next = new ListNode(sum%10);
            cur = cur.next;
        }
        if(count!=0)
            cur.next = new ListNode(count);
        return c.next;
    }
    public static ListNode removeNthToEnd(ListNode a , int k)
    {
        ListNode a1  = a;
        List<Integer> list = new ArrayList<>();
        while(a1!=null)
        {
            list.add(a1.val);
            a1 = a1.next;
        }
        int n = list.size();
        list.remove(n-k);
        ListNode ans =  new ListNode(0);
        a1 =ans;
        for(int i=0;i< list.size();i++)
        {
            a1.next = new ListNode(list.get(i));
            a1 = a1.next;
        }
        return ans.next;
    }
    public static ListNode swaqPairs(ListNode a)
    {
        ListNode one1 = new ListNode(0);
        ListNode  two1 = new ListNode(0);
        ListNode one = one1;
        ListNode two = two1;
        ListNode a1 = a;
        int cnt =1;
        while(a1!=null)
        {

            if(cnt%2!=0)
            {
                one.next = new ListNode(a1.val);
                one  = one.next;
            }
            else{
                two.next = new ListNode(a1.val);
                two = two.next;
            }
            cnt++;
            a1= a1.next;
        }
        ListNode ans =new ListNode(0);
        a1 = ans;
        one1 =one1.next;
        two1  = two1.next;
        while(one1!=null||two1!=null)
        {
            if(two1!=null)
            {
                a1.next = two1;
                two1 = two1.next;
                a1 = a1.next;
            }
            if(one1!=null)
            {
                a1.next = one1;
                one1 = one1.next;
                a1= a1.next;
            }

        }

        return ans.next;
    }
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode ans = new ListNode(0);
        ListNode res =ans;
        ListNode one = head;
        while(one!=null)
        {
            ListNode check = one;
            int cnt =0;
            for(int i=0;i<k&&check!=null;i++){
                check = check.next;
                cnt++;
            }
            if(cnt!=k)
            {
                res.next =one;
                break;
            }
            ListNode two = one;
            for(int i=1;i<k;i++)
            {
                one = one.next;
            }
            ListNode three = one.next;
            one.next = null;
            res.next = reverseList(two);
            while(res.next!=null)
            {
                res = res.next;
            }
            one = three;

        }
     return ans.next;
    }
    public static ListNode copyRandom(ListNode a)
    {
      HashMap<ListNode,ListNode> has = new HashMap<>();
      ListNode b = a;
      while(b!=null)
      {
          ListNode clone = new ListNode(b.val);
          has.put(b,clone);
          b = b.next;
      }
      b =a;
      while (b!=null)
      {
          ListNode c = has.get(b);
          c.next = has.get(b.next);
          c.random = has.get(b.random)==null?null:has.get(b.random);
          b = b.next;
      }
      return has.get(a);

    }
    public static ListNode sortList(ListNode a)
    {
        List<Integer> list = new ArrayList<>();
        ListNode b =a;
        while(b!=null)
        {
            list.add(b.val);
            b =b.next;
        }
        Collections.sort(list);
        ListNode ans = new ListNode(0);
        ListNode c = ans;
       for(int i=0;i<list.size();i++)
        {
            c.next = new ListNode(list.get(i));
            c=  c.next;
        }
       return ans.next;
   }
   public static ListNode mergeKList(ListNode[] lists)
   {
       List<ListNode> ans =new ArrayList<>();
       for(ListNode list : lists)
       {
           while(list!=null)
           {
               ans.add(list);
               list= list.next;
           }
       }
       Collections.sort(ans,(a,b)->{
           return a.val-b.val;
       });
       ListNode res = new ListNode(0);
       ListNode r = res;
       for(int i=0;i< ans.size();i++)
       {
           r.next = ans.get(i);
           r= r.next;
       }
       return res;

   }
    public static void printRandomList(ListNode head) {
        // 先记录每个节点的索引位置，方便 random 映射
        Map<ListNode, Integer> indexMap = new HashMap<>();
        ListNode cur = head;
        int idx = 0;
        while (cur != null) {
            indexMap.put(cur, idx++);
            cur = cur.next;
        }

        // 再打印
        cur = head;
        System.out.print("[");
        while (cur != null) {
            String rand = (cur.random == null) ? "null" : String.valueOf(indexMap.get(cur.random));
            System.out.print("[" + cur.val + "," + rand + "]");
            cur = cur.next;
            if (cur != null) System.out.print(",");
        }
        System.out.println("]");
    }





    public static void main(String[] args) {
        //TreeNode
//        int[] arr = {1,2,3,4,5,6,7};
//        TreeNode t1 = sortedArrayToBST(arr,0,arr.length-1);
//        List<Integer> list = new ArrayList<>();
//        list = inorderTraversal(list,t1);
//        System.out.println("中序遍历： ");
//        for(int i=0;i<list.size();i++)
//            System.out.print(list.get(i)+",");


        //ListNode
        //记得先余留值在往后遍历
        ListNode a = new ListNode(1);
        ListNode a1 = a;
        for (int i = 2; i < 6; i++) {
            a1.next = new ListNode(i);
            a1 = a1.next;
        }
        ListNode b = new ListNode(6);
        ListNode b1 = b;
        for (int i = 7; i <= 10; i++) {
            b1.next = new ListNode(i);
            b1 = b1.next;
        }
      List<Integer[]> list = new ArrayList<>();
        list.add(new Integer[]{7,null});
        list.add(new Integer[]{13,0});
        list.add(new Integer[]{11,4});
        list.add(new Integer[]{10,2});
        list.add(new Integer[]{1,0});
        ListNode[] nodes = new ListNode[list.size()];
        for(int i=0;i<list.size();i++)
        {
            nodes[i] = new ListNode(list.get(i)[0]);
        }
        for(int i=0;i<list.size();i++)
        {
            if(i+1< list.size())
            {
                nodes[i].next = nodes[i+1];

            }
            if(  list.get(i)[1]!=null)
            {
                nodes[i].random = nodes[list.get(i)[1]];
            }
        }
       System.out.println("原链表：");
        HashMap<ListNode,Integer> has= new HashMap<>();
        int idx =0;
        for(int i=0;i<list.size();i++)
        {
            has.put(nodes[i],idx++);
        }
        for(int i=0;i< list.size();i++) {
            System.out.print(nodes[i].val);
            System.out.println(has.get(nodes[i].random));
        }
        ListNode h = copyRandom(nodes[0]);
        printRandomList(h);
//        ListNode g = reverseKGroup(a,2);
//        g = sortList(g);
//        while(g!=null)
//        {
//            System.out.println(g.val);
//            g =g.next;
//        }
//
//        e = e1;
//              e = copyRandom(e);
//        while (e!=null) {
//            System.out.println(e.val);
//            if(e.random!=null)
//                System.out.println(e.random.val);
//            e= e.next;
//        }


//        ListNode f = reverseKGroup(a,2);
//        while(f!=null)
//        {
//            System.out.print(f.val);
//            f= f.next;
//        }

//        ListNode e = swaqPairs(a);
//        while(e!=null)
//        {
//            System.out.println(e.val);
//            e= e.next;
//        }
//        ListNode  d = removeNthToEnd(a,1);
//        while(d!=null)
//        {
//            System.out.println(d.val);
//            d=d.next;
//        }

//        ListNode c = addToNumbers(a, b);
//        while (c != null) {
//            System.out.print(c.val);
//            c = c.next;
//        }

//        boolean flag = isHuiWen(a);
//        System.out.println(flag);

//        boolean flag1= hasCycle(a);
//        System.out.println(flag1);

//        while(a2!=null)
//        {
//            System.out.println(a2.val);
//            a2= a2.next;
//        }
//       ListNode xiangjiao =  getIntersectionNode(a,b);
//        System.out.println(xiangjiao);
//        ListNode c =merge(a,b);
//        while(c!=null)
//        {
//            System.out.print(c.val+",");
//            c=c.next;
//        }
//    }

    }
}
//静态方法（static）可以调用：
//
//        其他静态方法（同类中可以直接调用，或用类名调用）
//
//        静态变量（直接用或用类名访问）
//
//        非静态方法/变量 —— 只能通过对象实例调用，不能直接用
//大顶堆小顶堆
//lru